We propose an online convex optimization algorithm (RescaledExp) that achieves optimal regret in the unconstrained setting without prior knowledge of any bounds on the loss functions. We prove a lower bound showing an exponential separation between the regret of existing algorithms that require a known bound on the loss functions and any algorithm that does not require such knowledge. RescaledExp matches this lower bound asymptotically in the number of iterations. RescaledExp is naturally hyperparameter-free and we demonstrate empirically that it matches prior optimization algorithms that require hyperparameter optimization.

This is a practically important optimization problem, as many machine learning problems can be reduced to it (via online to batch conversion). The paper does a nice job explaining the history of this problem. This paper is the first that lifts the assumption to know an a priori bound on the norms of the gradients of the loss functions and achieves an almost linear dependency on the norm of the competitor. The authors prove a lower bound on regret of any algorithm (Theorem 2.1). The lower bound shows that regret can be exponential in the worst case if the norms of the gradients grow too rapidly.

We propose an online convex optimization algorithm (RescaledExp) that achieves optimal regret in the unconstrained setting without prior knowledge of any bounds on the loss functions. We prove a lower bound showing an exponential separation between the regret of existing algorithms that require a known bound on the loss functions and any algorithm that does not require such knowledge. RescaledExp matches this lower bound asymptotically in the number of iterations. RescaledExp is naturally hyperparameter-free and we demonstrate empirically that it matches prior optimization algorithms that require hyperparameter optimization. Papers published at the Neural Information Processing Systems Conference.